package Day_Practice;

public class Practice01 {
    //精选入门第1题，二位数组双边都增
    boolean Find (int target,int[][] array){
        int i=0;
        int j= array.length-1;
        while(i < array.length && j> 0){
            if (target<array[i][j]){
                j--;
            } else if (target>array[i][j]) {
                i++;
            }else {
                return true;
            }
        }
        return false;
    }
    //精选入门第5题
    public int minNumberInRotateArray1 (int[] nums) {
        if (nums==null||nums.length==0){
            return 0;
        }
        int left=0;
        int right=nums.length-1;
        int mid=0;
        //while条件，如果nums[left]大于等于nums[right]，说明此时的两个nums[left]和nums[right]依然属于不同的两部分
        while(nums[left]>=nums[right]){//left<right也可以
            //说明相邻，则取右侧下标给mid
            if (right-left==1){
                mid =right;
                break;
            }
            mid=(left+right)/2;
            if (nums[left]==nums[right]&&nums[mid]==nums[left]){
                //这部分线性查找最小值
                int result=nums[left];
                for (int i=left+1;i<right;i++){
                    if (nums[i]<result){
                        result=nums[i];
                    }
                    //如果nums[i]>result就继续i++
                }
                return result;
            }
            if (nums[mid]>=nums[left]){
                //从left到mid中间值依然属于前半部分，找最小值到右边寻找
                left=mid;
            } else if(nums[mid]<nums[right]){
                //从mid到right的部分值完全属于后半部分，找最小值到左边寻找
                right=mid;
            }
        }
        return nums[mid];
    }

    public int minNumberInRotateArray(int [] array) {
        if(array == null || array.length == 0){
            return 0;
        }
        int left = 0;
        int right = array.length - 1;
        int mid = 0;
        while(array[left] >= array[right]){
            if(right - left == 1){
                mid = right;
                break;
            }
            mid = left + ((right - left)>>1);
            if(array[left] == array[right] && array[mid] == array[left]){ //1
                int result = array[left];
                for(int i = left+1; i < right; i++){ //left和right值是相等的
                    if(array[i] < result){
                        result = array[i];
                    }
                }
                return result;
            }
            if(array[mid] >= array[left]){
                left = mid;
            }
            else{
                right = mid;
            }
        }
        return array[mid];
    }
    //奇偶数
    public void func(int[] arr){
        int left=0;
        int right=arr.length;
        while (left<right)
        {
            while(left < right && arr[left]%2!=0){
                left++;//奇数向后移动
            }
            while (left < right && arr[right]%2==0){
                right--;//偶数向前移动
            }
            //走到这里一定出现偶数在前部分，奇数在后部分的情况
            if(left < right ){
                int tmp=arr[left];
                arr[left]=arr[right];
                arr[right]=tmp;
            }
        }
    }
     


}
